import java.util.Arrays;
import java.util.Scanner;

public class Test {

    public static void main(String[] args) {
        int[] arr = {5,7,7,8,8,10};
        arr = searchRange(arr,8);
        System.out.println(Arrays.toString(arr));
    }
    //34.寻找首尾位置
    public static int[] searchRange(int[] nums, int target) {
        int[] arr = {-1,-1};
        if(nums == null) {
            return arr;
        }
        if(nums.length == 1 && nums[0]==target) {
            arr[0] = 0;
            arr[1] = 0;
        }
        int left = 0;
        int right = nums.length-1;
        //1.寻找左端点
        while(left < right) {
            int mid = left + (right-left)/2;
            if(nums[mid] <target) {
                left = mid+1;
            }else {
                right = mid;

            }
        }
        if(nums[left] == target) {
            arr[0] = right;
        }
        left = 0;
        right = nums.length-1;
        //2.寻找右端点
        while(left < right) {
            int mid = left + (right-left+1)/2;
            if(nums[mid] <= target) {
                left = mid;
            }else {
                right = mid-1;
            }
        }
        if(nums[right] == target) {
            arr[1] = right;
        }
        return arr;
    }
    //35.寻找插入位置
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right=nums.length-1;
        while(left <= right) {
            int mid = left +(right-left)/2;
            if(nums[mid]>target) {
                right = mid-1;
            }else if(nums[mid] < target) {
                left = mid+1;
            }else {
                return mid;
            }
        }
        return right+1;
    }

}
